// This is JDefenceTower, a simple tower defence style game
//
// Copyright (C) 2010 Maximilian Junker
//
// This program is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free Software
// Foundation; either version 3 of the License, or (at your option) any later
// version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
// details.
//
// You should have received a copy of the GNU General Public License along with
// this program; if not, see <http://www.gnu.org/licenses/>.

package junker.defence.model;

import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class Grid {

	private int					sizeX;
	private int					sizeY;
	private MapLocation		sink;
	private DistanceNode[][]	distanceGraph;
	private boolean	doCalculateShortestPaths=true;
	private boolean	needsRecalculating=false;

	Grid(int sizeX, int sizeY, MapLocation sink) {
		// sizeX * sizeY is a rough upper bound for the length of a path
		assert sizeX * sizeY <= Integer.MAX_VALUE;
		assert sink.getX() <= sizeX && sink.getY() <= sizeY;
		this.sizeX = sizeX;
		this.sizeY = sizeY;
		this.sink = sink;
		this.distanceGraph = new DistanceNode[sizeX+1][sizeY+1];
		initializeDistanceGraph();
		calculateShortestPaths();
	}

	private void initializeDistanceGraph() {
		for (int x = 0; x <= sizeX; x++)
			for (int y = 0; y <= sizeY; y++) {
				distanceGraph[x][y] = new DistanceNode(new MapLocation(x, y),
						null, Integer.MAX_VALUE, false);
			}
		for (int x = 0; x <= sizeX; x++)
			for (int y = 0; y <= sizeY; y++) {
				if (x < sizeX)
					distanceGraph[x][y].addNeighbour(distanceGraph[x + 1][y]);
				if (y < sizeY)
					distanceGraph[x][y].addNeighbour(distanceGraph[x][y + 1]);
				if (x > 0)
					distanceGraph[x][y].addNeighbour(distanceGraph[x - 1][y]);
				if (y > 0)
					distanceGraph[x][y].addNeighbour(distanceGraph[x][y - 1]);
			}
	}

	private void calculateShortestPaths() {
		if(!doCalculateShortestPaths){
			this.needsRecalculating=true;
			return;
		}
		SortedSet<DistanceNode> nodes = new TreeSet<DistanceNode>(
				new Comparator<DistanceNode>() {
					@Override
					public int compare(DistanceNode o1, DistanceNode o2) {
						return o1.distance > o2.distance ? 1
								: (o1.distance < o2.distance ? -1 : new Integer(o1.hashCode()).compareTo(o2.hashCode()));
					}
				});
		// Initialize node set
		for (int x = 0; x <= sizeX; x++)
			for (int y = 0; y <= sizeY; y++) {
				if (x != sink.getX() || y != sink.getY()) {
					distanceGraph[x][y].predecessor = null;
					distanceGraph[x][y].distance = Integer.MAX_VALUE; // infinity
					if (!distanceGraph[x][y].blocked)
						nodes.add(distanceGraph[x][y]);
				} else {
					distanceGraph[x][y].predecessor = null;
					distanceGraph[x][y].distance = 0;
					nodes.add(distanceGraph[x][y]);
				}
			}

		// Dijkstra!
		while (!nodes.isEmpty()) {
			DistanceNode node = nodes.first();
			nodes.remove(node);
			for (DistanceNode n : node.neighbours) {
				if (!n.blocked && nodes.contains(n)) {
					if (node.distance + 1 < n.distance) {
						//remove & add, to keep set sorted
						nodes.remove(n);
						n.distance = node.distance + 1;
						n.predecessor = node;
						nodes.add(n);
					}
				}

			}
		}

	}

	boolean isBlocked(MapLocation loc) {
		assert loc.getX() <= sizeX;
		assert loc.getY() <= sizeY;

		return distanceGraph[(int)loc.getX()][(int)loc.getY()].blocked;
	}

	void blockLocation(MapLocation loc) {
		assert loc.getX() <= sizeX;
		assert loc.getY() <= sizeY;

		distanceGraph[(int)loc.getX()][(int)loc.getY()].blocked = true;
		calculateShortestPaths();
	}

	void unblockLocation(MapLocation loc) {
		assert loc.getX() <= sizeX;
		assert loc.getY() <= sizeY;

		distanceGraph[(int)loc.getX()][(int)loc.getY()].blocked = false;
		calculateShortestPaths();
	}
	
	Path findShortestPath(List<MapLocation> startingPoints){
		for(MapLocation l:startingPoints){
			assert(l.getX() <= sizeX); 
			assert(l.getY() <= sizeY);
		}
		
		DistanceNode shortest = null;
		DistanceNode current = null;
		Path shortestPath = new Path();
		for(MapLocation sp:startingPoints){
			current=distanceGraph[(int)sp.getX()][(int)sp.getY()];
			if(null==shortest || current.distance<shortest.distance){
				shortest=current;
			}
		}
		
		current=shortest;
		
		while(null!=current){
			shortestPath.add(new MapLocation(current.location.getX(),current.location.getY()));
			current=current.predecessor;			
		}
		return shortestPath;
	}

	/**
	 * Represents nodes in the distance graph, used for implementing a Dijkstra
	 * style algorithm to find shortest paths through the grid
	 */
	private class DistanceNode {
		DistanceNode		predecessor;
		int					distance;
		boolean				blocked;
		MapLocation		location;
		List<DistanceNode>	neighbours	= new LinkedList<DistanceNode>();

		DistanceNode(MapLocation location, DistanceNode predecessor,
				int distance, boolean blocked) {
			super();
			this.predecessor = predecessor;
			this.distance = distance;
			this.blocked = blocked;
			this.location = location;
		}

		public void addNeighbour(DistanceNode distanceNode) {
			neighbours.add(distanceNode);
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			DistanceNode other = (DistanceNode) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (blocked != other.blocked)
				return false;
			if (distance != other.distance)
				return false;
			if (predecessor == null) {
				if (other.predecessor != null)
					return false;
			} else if (!predecessor.equals(other.predecessor))
				return false;
			return true;
		}

		private Grid getOuterType() {
			return Grid.this;
		}

	}

	public void disableShortestPathCalculation() {
		this.doCalculateShortestPaths=false;
	}

	public void enableShortestPathCalculation() {
		this.doCalculateShortestPaths=true;
		if(needsRecalculating){
			calculateShortestPaths();
			this.needsRecalculating=false;
		}
	}

}
